#include <iostream>
#include <string>
#include <cstring>
#include <vector>

using namespace std;

//27.12 %
class Solution
{
  public:
	string minWindow(string s, string t)
	{
		if (s.empty() || t.empty() || (s.size() < t.size()))
			return "";
		int freq1[256] = {0};
		int freq2[256] = {0};
		for (int i = 0; i < t.size(); i++)
		{
			freq1[t[i]]++;
			freq2[s[i]]++;
		}
		int l = 0, r = t.size() - 1, res = 0, rel = s.size() + 1;
		while (l < s.size())
		{
			if (check(freq2, freq1))
			{
				if (r - l + 1 < rel)
				{
					res = l;
					rel = r - l + 1;
				}
				freq2[s[l++]]--;
			}
			else
			{
				if (r == s.size())
					break;
				freq2[s[++r]]++;
			}
		}
		if (rel == s.size() + 1)
			return "";
		return s.substr(res, rel);
	}
	bool check(int *a, int *b)
	{
		for (int i = 'A'; i < 'z'; i++)
		{
			if (a[i] < b[i])
			{
				return false;
			}
		}
		return true;
	}
};

int main()
{
	string S = "ADOBECODEBANC";
	string T = "ABC";
	cout << Solution().minWindow(S, T) << endl;
	return 0;
}
